﻿using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 爬楼梯
    {
        public class Solution
        {
            /// <summary>
            /// 超出时间限制
            /// https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn854d/
            /// </summary>
            /// <param name="n"></param>
            /// <returns></returns>
            public int ClimbStairs(int n)
            {

                if (n == 1) return 1;
                if (n == 2) return 2;

                return ClimbStairs(n - 1) + ClimbStairs(n - 2);
            }

            /// <summary>
            /// 迭代 
            /// 执行用时：36 ms, 在所有 C# 提交中击败了98.58%的用户
            /// 内存消耗：14.8 MB, 在所有 C# 提交中击败了75.13%的用户
            /// </summary>
            /// <param name="n"></param>
            /// <returns></returns>
            public int ClimbStairs2(int n)
            {
                if (n == 1) return 1;
                if (n == 2) return 2;
                int[] nums = new int[n];
                nums[0] = 1;
                nums[1] = 2;
                int i;
                for (i = 2; i < n; i++)
                {
                    nums[i] = nums[i - 1] + nums[i - 2];
                }
                return nums[n - 1];
            }
        }
        ITestOutputHelper output;

        public 爬楼梯(ITestOutputHelper output)
        {
            this.output = output;
        }


        [Fact]
        public void Test1()
        {

            Solution S = new Solution();

            output.WriteLine("" + S.ClimbStairs(2));
            output.WriteLine("" + S.ClimbStairs(3));
            output.WriteLine("" + S.ClimbStairs(44));
            output.WriteLine("");



            output.WriteLine("" + S.ClimbStairs2(2));
            output.WriteLine("" + S.ClimbStairs2(3));
            output.WriteLine("" + S.ClimbStairs2(44));
            output.WriteLine("");
        }
    }
}
